package com.fjl.list.leetcode206;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/24 11:06
 */
/*
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class ReverseKGroupClass {
    /*
    发现了递归性质，就可以得到大致的算法流程：
    1、先反转以 head 开头的 k 个元素。这里可以复用前面实现的 reverseN 函数。
    2、将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
    3、将上述两个过程的结果连接起来。
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a= head,b= head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转了
            if (b == null) {
                return head;
            }
            b = b.next;
        }
        ListNode newHead = reverseN(a, k);
        a.next = reverseKGroup(b, k);
        return newHead;
    }

    // 将链表的前 n 个节点反转（n <= 链表长度）
    ListNode reverseN(ListNode head, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (n > 0) {
            cur.next = pre;
            pre = cur;
            cur = nxt;
            n--;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        head.next = cur;
        return pre;
    }
}
